CoinChangeCoinRespect.java

packagesection12_Backtracking;

publicclassCoinChangeCoinRespect {

publicstaticvoidmain(String[] args) {
int[] denominations = { 2, 3, 5, 6 };
intamount = 10;
Stringans = "";
intcurrentCoinPosition = 0;

coinChange(denominations, amount, ans, currentCoinPosition);

 }

staticvoidcoinChange(int[] coins, intamount, Stringans, intcoinIndex) {

if (amount < 0)
return;

if (amount == 0) {
System.out.println(ans);
return;
 }

if (coinIndex > coins.length - 1)
return;

// include current coin
coinChange(coins, amount - coins[coinIndex], ans + coins[coinIndex], coinIndex);

// do not include current coin
coinChange(coins, amount, ans, coinIndex + 1);

 }
}

/* output:
22222
2233
226
235
55
*/